package other.dp;

/**
 * Created by Hyman on 2017/3/17.
 *
 * 最长公共子序列（Longest Common Subsequence, LCS），顾名思义，是指在所有的子序列中最长的那一个
 * 求解算法：对于母串X=<x1,x2,⋯,xm>, Y=<y1,y2,⋯,yn>，求LCS与最长公共子串
 * 假设Z=<z1,z2,⋯,zk>Z=<z1,z2,⋯,zk>是XX与YY的LCS， 我们观察到

 * 如果xm=yn，则zk=xm=yn，有Zk−1是Xm−1与Yn−1的LCS；
 * 如果xm≠ynx，则Zk是Xm与Yn−1的LCS，或者是Xm−1与Yn的LCS。
 * 因此，求解LCS的问题则变成递归求解的两个子问题。
 * 但是，上述的递归求解的办法中，重复的子问题多，效率低下。
 * 改进的办法——用空间换时间，用数组保存中间状态，方便后面的计算。这就是动态规划（DP)的核心思想了。
 *
 * http://blog.csdn.net/Alex123980/article/details/52316320
 */
public class LongestCommonSubsequence {

    public static void main(String[] args) {

        String s1 = "cnblogs";
        String s2 = "belong";

        System.out.println(lcs(s1, s2));

    }

    public static int lcs(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int c[][] = new int[len1+1][len2+1];
        for (int i = 0; i <= len1; i++) {
            for( int j = 0; j <= len2; j++) {
                if(i == 0 || j == 0) {
                    c[i][j] = 0;
                } else if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    c[i][j] = c[i-1][j-1] + 1;
                } else {
                    c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
                }
            }
        }
        for (int i = 0; i <= len1; i++) {
            for( int j = 0; j <= len2; j++) {
                System.out.print(c[i][j] + " ");
            }
            System.out.println();
        }


        return c[len1][len2];
    }
}
